package class20;

/**
 * @author YZY
 * @since 2022/8/20 14:14
 * <a href="https://leetcode.cn/problems/longest-palindromic-subsequence/">516. 最长回文子序列</a>
 * 方法二：范围尝试模型，判断所有情况，这道题是只需要管 str[L...R] 上，那么有四种情况
 * 1 最长的回文子序列 不在L上，不在R上
 * 2 最长的回文子序列 在L上，不在R上
 * 3 最长的回文子序列 不在L上，在R上
 * 4 最长的回文子序列 在L上，在R上
 * 分析出全部情况后，直接尝试代码
 */
public class Code01_PalindromeSubsequence2 {

    // 暴力尝试
    public static int longestPalindromeSubseq1(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        char[] str = s.toCharArray();
        return process1(str, 0, str.length - 1);
    }

    private static int process1(char[] str, int L, int R) {
        // 只有一个字符的时候，那么回文就只有1个
        if (L == R) {
            return 1;
        }
        // 当仅剩两个字符的时候，如果L和R上的字符相等，那么就是两个回文，否则自身就是1个
        if (L == R - 1) {
            return str[L] == str[R] ? 2 : 1;
        }
        int case1 = process1(str, L + 1, R - 1);
        int case2 = process1(str, L, R - 1);
        int case3 = process1(str, L + 1, R);
        // 当在L和R上的时候，需要做个判断是否相同，相同的话那么回文字符又加了2个，所以需要加2
        int case4 = str[L] == str[R] ? 2 + process1(str, L + 1, R - 1) : 0;
        return Math.max(Math.max(case1, case2), Math.max(case3, case4));
    }

    // 记忆化搜索
    public static int longestPalindromeSubseq2(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        char[] str = s.toCharArray();
        int[][] dp = new int[str.length][str.length];
        return process2(str, 0, str.length - 1, dp);
    }

    private static int process2(char[] str, int L, int R, int[][] dp) {
        if (dp[L][R] != 0) {
            return dp[L][R];
        }
        // 只有一个字符的时候，那么回文就只有1个
        if (L == R) {
            return 1;
        }
        // 当仅剩两个字符的时候，如果L和R上的字符相等，那么就是两个回文，否则自身就是1个
        if (L == R - 1) {
            return str[L] == str[R] ? 2 : 1;
        }
        int case1 = process2(str, L + 1, R - 1, dp);
        int case2 = process2(str, L, R - 1, dp);
        int case3 = process2(str, L + 1, R, dp);
        // 当在L和R上的时候，需要做个判断是否相同，相同的话那么回文字符又加了2个，所以需要加2
        int case4 = str[L] == str[R] ? 2 + process2(str, L + 1, R - 1, dp) : 0;
        return dp[L][R] = Math.max(Math.max(case1, case2), Math.max(case3, case4));
    }

    // 动态规划
    public static int longestPalindromeSubseq3(String s) {
        char[] str = s.toCharArray();
        int n = str.length;
        int[][] dp = new int[n][n];
        dp[n - 1][n - 1] = 1;
        for (int i = 0; i < n - 1; ++i) {
            dp[i][i] = 1;
            dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
        }
        for (int L = n - 1 - 2; L >= 0; --L) {
            for (int R = L + 2; R < n; ++R) {
                int case1 = dp[L + 1][R - 1];
                int case2 = dp[L][R - 1];
                int case3 = dp[L + 1][R];
                int case4 = str[L] == str[R] ? 2 + dp[L + 1][R - 1] : 0;
                dp[L][R] = Math.max(Math.max(case1, case2), Math.max(case3, case4));
            }
        }
        return dp[0][n - 1];
    }

}
